package zw_1_100.zw_6_Z字形变换;

import java.util.ArrayList;
import java.util.List;

class Solution {

    public static void main(String[] args) {
        String s = "PAYPALISHIRING";
        int numRows = 4;
        String s1 = convert(s, numRows);
        System.out.println(s1);
    }


    /**
     * 算法流程： 按顺序遍历字符串 s；
     * res[i] += c： 把每个字符 c 填入对应行 si；
     * i += flag： 更新当前字符 c 对应的行索引；
     * flag = - flag： 在达到 Z 字形转折点时，执行反向。
     * 复杂度分析：
     * 时间复杂度 O(N)：遍历一遍字符串 s；
     * 空间复杂度 O(N)：各行字符串共占用 O(N) 额外空间。
     *
     * @param s
     * @param numRows
     * @return
     */
//    public static String convert(String s, int numRows) {
//        if (numRows < 2) return s;
//        List<StringBuilder> rows = new ArrayList<>();
//        for (int i = 0; i < numRows; i++) rows.add(new StringBuilder());
//        int i = 0, flag = -1;
//        for (char c : s.toCharArray()) {
//            rows.get(i).append(c);
//            if (i == 0 || i == numRows - 1) flag = -flag;
//            i += flag;
//        }
//        StringBuilder res = new StringBuilder();
//        for (StringBuilder row : rows) res.append(row);
//        return res.toString();
//    }


    /**
     * 自己写的
     * 根据 i % (2 * numRows - 2) 判断索引
     * @param s
     * @param numRows
     * @return
     */
    public static String convert(String s, int numRows) {
        if(numRows < 2  || s.length() <= numRows ) return s;
        List<StringBuilder> rows = new ArrayList<>();
        for (int i = 0; i < numRows; i++) rows.add(new StringBuilder());
        int row;
        for (int i = 0; i < s.length(); i++) {
            if (i % (2 * numRows - 2) < numRows) {
                row = i % (2 * numRows - 2);
            } else {
                row = (2 * numRows - 2) - i % (2 * numRows - 2);
            }
            rows.get(row).append(s.charAt(i));
        }
        StringBuilder res = new StringBuilder();
        for (StringBuilder r : rows) res.append(r);
        return res.toString();
    }
}
